// Copyright 2000-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
package com.intellij.util.containers.hash;


import org.jetbrains.annotations.NotNull;

import java.util.Arrays;


final class HashUtil {
  static final int MIN_CAPACITY = 5;

  static final float DEFAULT_LOAD_FACTOR = 1;

  static final float CAPACITY_MULTIPLE = 1.618033989f;


  public static int hash(Object key) {

    return key == null ? 0 : key.hashCode() & 0x7fffffff;
  }

  public static <K> int hash(K key, @NotNull EqualityPolicy<? super K> hashingStrategy) {
    return key == null ? 0 : hashingStrategy.getHashCode(key) & 0x7fffffff;
  }


  static int adjustTableSize(int size) {

    int i = Arrays.binarySearch(tableSizes, size);

    if (i < 0) {

      i = ~i;
    }

    return tableSizes[i];
  }


  private static final int[] tableSizes = {


    // include all odd primes under 1000

    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,

    71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,

    149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,

    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,

    307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,

    389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,

    467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,

    571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,

    653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,

    751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,

    853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,

    947, 953, 967, 971, 977, 983, 991, 997,


    1031, 2063, 4127, 8263, 16529, 33071, 66161, 132329, 264659, 529327, 1058657, 2117317, 4234651, 8469319,

    1091, 2203, 4409, 8819, 17657, 35317, 70639, 141283, 282571, 565163, 1130351, 2260717, 4521509, 9043033,

    1153, 2309, 4621, 9257, 18517, 37039, 74093, 148193, 296437, 592877, 1185787, 2371609, 4743223, 9486469,

    1217, 2437, 4877, 9767, 19541, 39089, 78179, 156361, 312727, 625477, 1250969, 2501953, 5003909, 10007819,

    1283, 2579, 5167, 10337, 20681, 41381, 82763, 165527, 331063, 662141, 1324313, 2648629, 5297287, 10594583,

    1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819, 1403641, 2807303, 5614657, 11229331,

    1409, 2819, 5639, 11279, 22567, 45137, 90281, 180563, 361159, 722321, 1444649, 2889317, 5778649, 11557303,

    1481, 2963, 5927, 11863, 23741, 47491, 94993, 189989, 379979, 759959, 1519939, 3039917, 6079861, 12159731,

    1543, 3089, 6197, 12401, 24809, 49627, 99257, 198529, 397063, 794137, 1588289, 3176597, 6353213, 12706451,

    1601, 3203, 6421, 12853, 25717, 51437, 102877, 205759, 411527, 823117, 1646237, 3292489, 6584983, 13169977,

    1667, 3343, 6689, 13381, 26777, 53569, 107171, 214351, 428731, 857471, 1714957, 3429961, 6859933, 13719869,

    1733, 3467, 6947, 13901, 27803, 55609, 111227, 222461, 444929, 889871, 1779761, 3559537, 7119103, 14238221,

    1801, 3607, 7219, 14447, 28901, 57803, 115613, 231241, 462491, 924997, 1850021, 3700043, 7400123, 14800271,

    1861, 3727, 7457, 14923, 29851, 59707, 119417, 238837, 477677, 955363, 1910729, 3821483, 7643017, 15286079,

    1931, 3863, 7727, 15461, 30931, 61871, 123757, 247519, 495041, 990137, 1980281, 3960581, 7921169,

    1993, 3989, 7993, 15991, 31991, 63997, 127997, 256019, 512047, 1024099, 2048203, 4096427, 8192867,


    26339969, 52679969, 105359939, 210719881, 421439783, 842879579, 1685759167,

    28977863, 57955739, 115911563, 231823147, 463646329, 927292699, 1854585413,

    31322867, 62645741, 125291483, 250582987, 501165979, 1002331963, 2004663929,

    17135863, 34271747, 68543509, 137087021, 274174111, 548348231, 1096696463,

    18366923, 36733847, 73467739, 146935499, 293871013, 587742049, 1175484103,

    19845871, 39691759, 79383533, 158767069, 317534141, 635068283, 1270136683,

    21006137, 42012281, 84024581, 168049163, 336098327, 672196673, 1344393353,

    22458671, 44917381, 89834777, 179669557, 359339171, 718678369, 1437356741,

    23723597, 47447201, 94894427, 189788857, 379577741, 759155483, 1518310967,

    25002389, 50004791, 100009607, 200019221, 400038451, 800076929, 1600153859,


    Integer.MAX_VALUE,
  };

  static {

    Arrays.sort(tableSizes);
  }
}

